package class33;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MaxEOR {


    //O(N^2)
    public static int maxXorSubarray1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] eor = new int[arr.length];
        eor[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            eor[i] = eor[i - 1] ^ arr[i];
        }
        int max = Integer.MIN_VALUE;
        for (int j = 0; j < arr.length; j++) {
            for (int i = 0; i <= j; i++) {
                max = Math.max(max, i == 0 ? eor[j] : eor[j] ^ eor[i - 1]);
            }
        }
        return max;
    }


    public static class Node {
        public Node[] nexts = new Node[2];
    }

    public static class NumTrie {
        public Node head = new Node();

        //把某个数字newNum加入到这棵树的前缀树中
        //num是一个32位的整数，所以加入的过程一共走32步
        public void add(int newNum) {
            Node cur = head;
            for (int move = 31; move >= 0; move--) {
                //从高位到低位，取出每一位的状态，如果当前状态是0,path(int) = 0
                //如果当前状态是1,path(int) = 1
                int path = ((newNum >> move) & 1);
                //无路新建，有路复用
                cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
                cur = cur.nexts[path];
            }
        }

        //该结构之前收集了一些数字，并且建好了前缀树
        //eroi 和 ? ^ 最大结果返回
        public int maxXor(int eori) {
            Node cur = head;
            int res = 0;
            for (int move = 31; move >= 0; move--) {
                int path = (eori >> move) & 1;
                //期待的路

                //      若eori是正数，则符号位（最高位）为0，返回结果最大我们就需要一个数的符号位（最高位）也为0
                //      若eori是负数，则符号位（最高位）为1，返回结果最大我们就需要一个数的符号位（最高位）也为1
                //最高位上我总是期待与你原来的一样
                //   我们其他位置上不管正数还是负数我们尽可能保证从高位到低位最多的1
                //      正数我们很好理解，负数符号位为1，若其他位置全为1，则这个二进制数字表示-1。（负数十进制变二进制需要取反加一）
                //其他位置上我期待与你相反
                int best = move == 31 ? path : (path ^ 1);
                //实际走的路
                //若期待的路存在则有期待的路
                //期待的路不存在则走相反的路
                best = cur.nexts[best] != null ? best : (best ^ 1);
                //(path ^ best ) 当前位位异或完的结果
                res |= (path ^ best) << move;
                cur = cur.nexts[best];
            }
            return res;
        }
    }

    public static int maxXorSubarray2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        //0~i   异或和
        int eor = 0;
        NumTrie numTrie = new NumTrie();
        //一个数也没有的时候，异或和是0
        numTrie.add(0);
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];// 0...i  异或和
            //X  0~0  0~1  ...  0~i1
            max = Math.max(max, numTrie.maxXor(eor));
            numTrie.add(eor);
        }
        return max;
    }


    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxSize = 20;
        int maxValue = 20;
        int testTime = 200000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            int max1 = maxXorSubarray1(arr1);
            int max2 = maxXorSubarray2(arr2);
            if (max1 != max2) {
                System.out.println("出现错误了！");
                printArray(arr1);
                printArray(arr2);
                System.out.println(max1);
                System.out.println(max2);
                break;
            }
        }
        System.out.println("测试结束！");
    }


}
